package homework5;

/**
 * Knapsack calculate class
 * 
 * @author eDisOn
 * 
 */
public class Knapsack
{
	/**
	 * Knapsack calculate function
	 * 
	 * @param n
	 *            objects number
	 * @param values
	 *            objects values record
	 * @param weights
	 *            objects weights record
	 * @param max
	 *            maximum knapsack maximum weight
	 * @return maximum weight can put into knapsack
	 */
	public int knapsack(int n, int[] values, int weights[], int max)
	{
		int[] f = new int[max + 1];

		for (int i = 0; i < n; i++)
		{
			for (int j = max; j >= weights[i]; j--)
			{
				if (f[j] < f[j - weights[i]] + values[i])
				{
					f[j] = f[j - weights[i]] + values[i];
				}
			}
		}
		return f[max];
	}
}